package com.example.arithmeticleetcode.learnArithmetic2.graph;


import com.example.arithmeticleetcode.learnArithmetic2.union.GenericUnionFind;

import java.util.*;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2020-11-17 10:47
 **/
public class ListGraph<V, E> extends Graph<V, E> {

    private Map<V, Vertex<V, E>> vertics = new HashMap<>();
    private Set<Edge<V, E>> edges = new HashSet<>();
    private Comparator<Edge<V, E>> edgeComparator = (e1, e2) -> {
        return weightManager.compare(e1.weight, e2.weight);
    };

    public ListGraph(WeightManager<E> weightManager) {
        super(weightManager);
    }

    public ListGraph() {
    }

    public void print() {
        System.out.println("顶点----------------------------");
        vertics.forEach((V v, Vertex<V, E> vertex) -> {
            System.out.println(v);
            System.out.println("out---------");
            System.out.println(vertex.outEdges);
            System.out.println("in----------");
            System.out.println(vertex.inEdges);
        });
        System.out.println("边=========================");
        edges.forEach((Edge<V, E> edge) -> {
            System.out.println(edge);
        });

    }

    @Override
    public int edgesSize() {
        return edges.size();
    }

    @Override
    public int verticesSize() {
        return vertics.size();
    }

    @Override
    public void addVertext(V v) {
        if (vertics.containsKey(v)) return;
        vertics.put(v, new Vertex<>(v));

    }

    @Override
    public void addEdge(V from, V to) {
        addEdge(from, to, null);
    }

    @Override
    public void addEdge(V from, V to, E weight) {
        //判断from to 定点是否存在
        Vertex<V, E> fromVertex = vertics.get(from);
        if (fromVertex == null) {
            fromVertex = new Vertex<>(from);
            vertics.put(from, fromVertex);
        }

        Vertex<V, E> toVertex = vertics.get(to);
        if (toVertex == null) {
            toVertex = new Vertex<>(to);
            vertics.put(to, toVertex);
        }


        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        edge.weight = weight;
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }

        fromVertex.outEdges.add(edge);
        toVertex.inEdges.add(edge);

        edges.add(edge);


    }

    @Override
    public void removeVertext(V v) {
        Vertex<V, E> vertex = vertics.get(v);
        if (vertex == null) return;
        Iterator<Edge<V, E>> outIterator = vertex.outEdges.iterator();
        while (outIterator.hasNext()) {
            Edge<V, E> edge = outIterator.next();
            edge.to.inEdges.remove(edge);
            //将当前遍历到的元素从当前集合vertex.outEdges中删除掉
            outIterator.remove();
            edges.remove(edge);
        }

        Iterator<Edge<V, E>> inIterator = vertex.inEdges.iterator();
        while (inIterator.hasNext()) {
            Edge<V, E> edge = inIterator.next();
            edge.from.outEdges.remove(edge);
            //将当前遍历到的元素从当前集合vertex.inEdges中删除掉
            inIterator.remove();
            edges.remove(edge);
        }


    }

    @Override
    public void removeEdge(V from, V to) {
        Vertex<V, E> fromVertex = vertics.get(from);
        if (fromVertex == null) return;
        Vertex<V, E> toVertex = vertics.get(to);
        if (toVertex == null) return;
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(toVertex);
            edges.remove(edge);
        }
    }

    @Override
    public void bfs(V begin, VertexVisitor<V> vertexVisitor) {
        Vertex<V, E> beginVertex = vertics.get(begin);
        if (beginVertex == null) return;

        Queue<Vertex<V, E>> queue = new LinkedList<>();
        Set<Vertex<V, E>> visitedVertices = new HashSet<>();

        queue.offer(beginVertex);
        visitedVertices.add(beginVertex);

        while (!queue.isEmpty()) {
            Vertex<V, E> vertex = queue.poll();
            if (vertexVisitor.visit(vertex.value)) return;

            for (Edge<V, E> edge : vertex.outEdges) {
                if (visitedVertices.contains(edge.to)) continue;
                queue.offer(edge.to);
                visitedVertices.add(edge.to);
            }
        }

    }

    @Override
    public void dfs(V begin, VertexVisitor<V> vertexVisitor) {
        if (vertexVisitor == null) return;
        Vertex<V, E> beginVertex = vertics.get(begin);
        if (beginVertex == null) return;

        Stack<Vertex<V, E>> stack = new Stack<>();
        Set<Vertex<V, E>> vertexVisited = new HashSet<>();

        stack.push(beginVertex);
        vertexVisited.add(beginVertex);
        if (vertexVisitor.visit(beginVertex.value)) return;

        while (!stack.isEmpty()) {
            Vertex<V, E> vertex = stack.pop();
            for (Edge<V, E> edge : vertex.outEdges) {
                if (vertexVisited.contains(edge.to)) continue;
                vertexVisited.add(edge.to);
                stack.push(edge.from);
                stack.push(edge.to);
                if (vertexVisitor.visit(edge.to.value)) return;
                break;
            }
        }
    }

    //    @Override
//    public void bfs(V begin) {
//        Vertex<V, E> beginVertex = vertics.get(begin);
//        if (beginVertex == null) return;
//
//        Queue<Vertex<V, E>> queue = new LinkedList<>();
//        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
//
//        queue.offer(beginVertex);
//        visitedVertices.add(beginVertex);
//
//        while (!queue.isEmpty()) {
//            Vertex<V, E> vertex = queue.poll();
//            System.out.println(vertex.value);
//
//            for (Edge<V, E> edge : vertex.outEdges) {
//                if (visitedVertices.contains(edge.to)) continue;
//                queue.offer(edge.to);
//                visitedVertices.add(edge.to);
//            }
//        }
//    }
//
//    @Override
//    public void dfs(V begin) {
//        Vertex<V, E> beginVertex = vertics.get(begin);
//        if (beginVertex == null) return;
//        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
//        Stack<Vertex<V, E>> stack = new Stack<>();
//        stack.push(beginVertex);
//        visitedVertices.add(beginVertex);
//        System.out.println(beginVertex.value);
//        while (!stack.isEmpty()) {
//            Vertex<V, E> vertex = stack.pop();
//            for (Edge<V, E> edge : vertex.outEdges) {
//                if (visitedVertices.contains(edge.to)) continue;
//                stack.push(edge.from);
//                stack.push(edge.to);
//                System.out.println(edge.to.value);
//                visitedVertices.add(edge.to);
//                break;
//            }
//        }
//    }
//
//    public void dfs2(V begin) {
//        Vertex<V, E> beginVertex = vertics.get(begin);
//        if (beginVertex == null) return;
//        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
//        dfs2(beginVertex, visitedVertices);
//    }
//
//    private void dfs2(Vertex<V,E> vertex, Set<Vertex<V, E>> visitedVertices) {
//
//        System.out.println(vertex.value);
//        visitedVertices.add(vertex);
//
//        for (Edge<V, E> edge : vertex.outEdges) {
//            if (visitedVertices.contains(edge.to)) continue;
//            dfs2(edge.to, visitedVertices);
//        }
//    }

    @Override
    public List<V> topologicalSort() {
        List<V> list = new ArrayList<>();
        Queue<Vertex<V, E>> queue = new LinkedList<>();
        Map<Vertex<V, E>, Integer> map = new HashMap<>();
        //初始化 将度为0的节点放入队列
        vertics.forEach((v, vertex) -> {
            if (vertex.inEdges.size() == 0) {
                queue.add(vertex);
            } else {
                map.put(vertex, vertex.inEdges.size());
            }

        });

        while (!queue.isEmpty()) {
            Vertex<V, E> vertex = queue.poll();
            list.add(vertex.value);
            for (Edge<V, E> edge : vertex.outEdges) {
                Integer count = map.get(edge.to) - 1;
                if (count == 0) {
                    queue.offer(edge.to);
                } else {
                    map.put(edge.to, count);
                }
            }
        }

        return list;
    }

    @Override
    public Set<EdgeInfo<V, E>> mst() {
        return kruskal();
    }

    ////O(ElogE)
    private Set<EdgeInfo<V, E>> prim() {
        Iterator<Vertex<V, E>> iterator = vertics.values().iterator();
        if (!iterator.hasNext()) return null;
        Vertex<V, E> vertex = iterator.next();

        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
        Set<Vertex<V, E>> addedVertices = new HashSet<>();
        addedVertices.add(vertex);
        //
        MinHeap<Edge<V, E>> heap = new MinHeap<>(vertex.outEdges, edgeComparator);

        int edgeSize = vertics.size();
        while (!heap.isEmpty() && edgeInfos.size() < edgeSize) {
            Edge<V, E> edge = heap.remove();
            if (addedVertices.contains(edge.to)) continue;

            edgeInfos.add(edge.info());
            addedVertices.add(edge.to);
            heap.addAll(edge.to.outEdges);
        }

        //相当于最小堆 nlog(n)
//        PriorityQueue<Edge<V, E>> heap = new PriorityQueue<>((e1, e2) -> {
//            return 0;
//        });
//
//        for (Edge<V, E> edge : vertex.outEdges) {
//
//        }
        return edgeInfos;
    }

    //O(ElogE)
    private Set<EdgeInfo<V, E>> kruskal() {
        int edgeSize = vertics.size() - 1;
        if (edgeSize == -1) return null;
        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
        MinHeap<Edge<V, E>> heap = new MinHeap<>(edges, edgeComparator);

        GenericUnionFind<Vertex<V, E>> uf = new GenericUnionFind();
        vertics.forEach((V v, Vertex<V, E> vertics) -> {
            uf.makeSet(vertics);
        });

        while (!heap.isEmpty() && edgeInfos.size() <= edgeSize) {
            Edge<V, E> edge = heap.remove();
            if (uf.isSame(edge.from, edge.to)) continue;
            edgeInfos.add(edge.info());
            uf.union(edge.from, edge.to);
        }
        return edgeInfos;
    }

    @Override
    public Map<V, PathInfo<V, E>> shortesPath(V begin) {
        return dijkstra(begin);
    }

    private Map<V, PathInfo<V, E>> bellmanFord(V begin) {
        Vertex<V, E> beginVertex = vertics.get(begin);
        if (beginVertex == null) return null;

        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
        selectedPaths.put(begin, new PathInfo<>(weightManager.zero()));

        int count = vertics.size() - 1;
        //进行v-1此松弛操作 复杂度
        for (int i = 0; i < count; i++) {
            for (Edge<V, E> edge : edges) {
                PathInfo<V, E> fromPath = selectedPaths.get(edge.from.value);
                if (fromPath == null) continue;
                relaxForBellmanFord(edge, fromPath, selectedPaths);
            }
        }

        selectedPaths.remove(begin);
        return selectedPaths;
    }

    /**
     * 松弛操作
     *
     * @param edge     进行松弛的边
     * @param fromPath edge到from的最短路径信息
     * @param paths    存放其他店的最短路径信息
     */
    private boolean relaxForBellmanFord(Edge<V, E> edge, PathInfo<V, E> fromPath, Map<V, PathInfo<V, E>> paths) {

        //新的可选择的最短路径 beginVertex到edge.from的最短路径 + edge.weight
        E newWeight = weightManager.add(fromPath.weight, edge.weight);

        //以前的最短路径，beginVertex到edge.to的最短路径
        PathInfo<V, E> oldPathInfo = paths.get(edge.to.value);
        if (oldPathInfo != null && weightManager.compare(newWeight, oldPathInfo.weight) >= 0) return false;
        if (oldPathInfo == null) {
            oldPathInfo = new PathInfo<>();
            paths.put(edge.to.value, oldPathInfo);
        } else {
            oldPathInfo.edgeInfos.clear();
        }
        oldPathInfo.weight = newWeight;
        oldPathInfo.edgeInfos.addAll(fromPath.edgeInfos);
        oldPathInfo.edgeInfos.add(edge.info());

        return true;
    }


    private Map<V, PathInfo<V, E>> dijkstra(V begin) {
        Vertex<V, E> beginVertex = vertics.get(begin);
        if (beginVertex == null) return null;

        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
        Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
        paths.put(beginVertex, new PathInfo<>(weightManager.zero()));
        //初始化paths
//        for (Edge<V, E> edge : beginVertex.outEdges) {
//            PathInfo<V, E> pathInfo = new PathInfo<>();
//            pathInfo.weight = edge.weight;
//            pathInfo.edgeInfos.add(edge.info());
//            paths.put(edge.to, pathInfo);
//        }

        while (!paths.isEmpty()) {
            Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = getMinPath(paths);
            //minVertex离开桌面，对它的outEdges进行松弛操作
            Vertex<V, E> minVertex = minEntry.getKey();
            PathInfo<V, E> minPath = minEntry.getValue();
            selectedPaths.put(minVertex.value, minPath);
            paths.remove(minVertex);
            //对minVertex的outEdges进行松弛操作
            for (Edge<V, E> edge : minVertex.outEdges) {
                //如果edge.to一离开桌面，就没有必要再次离开桌面
                if (selectedPaths.containsKey(edge.to.value)) continue;
                relaxForDijkstra(edge, minPath, paths);
//                if (relaxForDijkstra(edge, minPath, paths)) {
//                    System.out.println("负权环");
//                    return null;
//                }
            }
        }
        selectedPaths.remove(begin);
        return selectedPaths;
    }

    /**
     * 松弛操作
     *
     * @param edge     进行松弛的边
     * @param fromPath edge到from的最短路径信息
     * @param paths    存放其他店的最短路径信息
     */
    private boolean relaxForDijkstra(Edge<V, E> edge, PathInfo<V, E> fromPath, Map<Vertex<V, E>, PathInfo<V, E>> paths) {
        //新的可选择的最短路径 beginVertex到edge.from的最短路径 + edge.weight
        E newWeight = weightManager.add(fromPath.weight, edge.weight);

        //以前的最短路径，beginVertex到edge.to的最短路径
        PathInfo<V, E> oldPathInfo = paths.get(edge.to);
        if (oldPathInfo != null && weightManager.compare(newWeight, oldPathInfo.weight) >= 0) return false;
        if (oldPathInfo == null) {
            oldPathInfo = new PathInfo<>();
            paths.put(edge.to, oldPathInfo);
        } else {
            oldPathInfo.edgeInfos.clear();
        }
        oldPathInfo.weight = newWeight;
        oldPathInfo.edgeInfos.addAll(fromPath.edgeInfos);
        oldPathInfo.edgeInfos.add(edge.info());
        return true;
    }


    private Map.Entry<Vertex<V, E>, PathInfo<V, E>> getMinPath(Map<Vertex<V, E>, PathInfo<V, E>> paths) {
        Iterator<Map.Entry<Vertex<V, E>, PathInfo<V, E>>> iterator = paths.entrySet().iterator();
        Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = iterator.next();
        while (iterator.hasNext()) {
            Map.Entry<Vertex<V, E>, PathInfo<V, E>> entry = iterator.next();
            if (weightManager.compare(entry.getValue().weight, minEntry.getValue().weight) < 0) {
                minEntry = entry;
            }
        }
        return minEntry;
    }

    @SuppressWarnings("unused")
    private Map<V, PathInfo<V, E>> bellmanFordForTeacher(V begin) {
        Vertex<V, E> beginVertex = vertics.get(begin);
        if (beginVertex == null) return null;

        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
        selectedPaths.put(begin, new PathInfo<>(weightManager.zero()));

        int count = vertics.size() - 1;
        for (int i = 0; i < count; i++) { // v - 1 次
            for (Edge<V, E> edge : edges) {
                PathInfo<V, E> fromPath = selectedPaths.get(edge.from.value);
                if (fromPath == null) continue;
                relaxForTeacher(edge, fromPath, selectedPaths);
            }
        }

//        for (Edge<V, E> edge : edges) {
//            PathInfo<V, E> fromPath = selectedPaths.get(edge.from.value);
//            if (fromPath == null) continue;
//            if (relaxForTeacher(edge, fromPath, selectedPaths)) {
//                System.out.println("有负权环");
//                return null;
//            }
//        }

        selectedPaths.remove(begin);
        return selectedPaths;
    }


    /**
     * 松弛
     *
     * @param edge     需要进行松弛的边
     * @param fromPath edge的from的最短路径信息
     * @param paths    存放着其他点（对于dijkstra来说，就是还没有离开桌面的点）的最短路径信息
     */
    private boolean relaxForTeacher(Edge<V, E> edge, PathInfo<V, E> fromPath, Map<V, PathInfo<V, E>> paths) {
        // 新的可选择的最短路径：beginVertex到edge.from的最短路径 + edge.weight
        E newWeight = weightManager.add(fromPath.weight, edge.weight);
        // 以前的最短路径：beginVertex到edge.to的最短路径
        PathInfo<V, E> oldPath = paths.get(edge.to.value);
        if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) >= 0) return false;

        if (oldPath == null) {
            oldPath = new PathInfo<>();
            paths.put(edge.to.value, oldPath);
        } else {
            oldPath.edgeInfos.clear();
        }

        oldPath.weight = newWeight;
        oldPath.edgeInfos.addAll(fromPath.edgeInfos);
        oldPath.edgeInfos.add(edge.info());

        return true;
    }

    private Map<V, PathInfo<V, E>> dijkstraForTeacher(V begin) {
        Vertex<V, E> beginVertex = vertics.get(begin);
        if (beginVertex == null) return null;

        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
        Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
        paths.put(beginVertex, new PathInfo<>(weightManager.zero()));
        // 初始化paths
//		for (Edge<V, E> edge : beginVertex.outEdges) {
//			PathInfo<V, E> path = new PathInfo<>();
//			path.weight = edge.weight;
//			path.edgeInfos.add(edge.info());
//			paths.put(edge.to, path);
//		}

        while (!paths.isEmpty()) {
            Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = getMinPath(paths);
            // minVertex离开桌面
            Vertex<V, E> minVertex = minEntry.getKey();
            PathInfo<V, E> minPath = minEntry.getValue();
            selectedPaths.put(minVertex.value, minPath);
            paths.remove(minVertex);
            // 对它的minVertex的outEdges进行松弛操作
            for (Edge<V, E> edge : minVertex.outEdges) {
                // 如果edge.to已经离开桌面，就没必要进行松弛操作
                if (selectedPaths.containsKey(edge.to.value)) continue;
                relaxForDijkstraForTeacher(edge, minPath, paths);
            }
        }

        selectedPaths.remove(begin);
        return selectedPaths;
    }

    /**
     * 松弛
     *
     * @param edge     需要进行松弛的边
     * @param fromPath edge的from的最短路径信息
     * @param paths    存放着其他点（对于dijkstra来说，就是还没有离开桌面的点）的最短路径信息
     */
    private void relaxForDijkstraForTeacher(Edge<V, E> edge, PathInfo<V, E> fromPath, Map<Vertex<V, E>, PathInfo<V, E>> paths) {
        // 新的可选择的最短路径：beginVertex到edge.from的最短路径 + edge.weight
        E newWeight = weightManager.add(fromPath.weight, edge.weight);
        // 以前的最短路径：beginVertex到edge.to的最短路径
        PathInfo<V, E> oldPath = paths.get(edge.to);
        if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) >= 0) return;

        if (oldPath == null) {
            oldPath = new PathInfo<>();
            paths.put(edge.to, oldPath);
        } else {
            oldPath.edgeInfos.clear();
        }

        oldPath.weight = newWeight;
        oldPath.edgeInfos.addAll(fromPath.edgeInfos);
        oldPath.edgeInfos.add(edge.info());
    }

    @Override
    public Map<V, Map<V, PathInfo<V, E>>> shortestPath() {
        Map<V, Map<V, PathInfo<V, E>>> paths = new HashMap<>();

        //初始化
        for (Edge<V, E> edge : edges) {

            Map<V, PathInfo<V, E>> map = paths.get(edge.from.value);
            if (map == null) {
                map = new HashMap<>();
                paths.put(edge.from.value, map);
            }
            PathInfo<V, E> pathInfo = new PathInfo<>(edge.weight);
            pathInfo.edgeInfos.add(edge.info());
            map.put(edge.to.value, pathInfo);
        }

        vertics.forEach((v2, vertex2) -> {
            vertics.forEach((v1, vertex1) -> {
                vertics.forEach((v3, vertex3) -> {
                    if (v1.equals(v2) || v2.equals(v3) || v1.equals(v3)) return;
                    //v1->v2
                    PathInfo<V, E> path12 = getPathInfo(v1, v2, paths);
                    if (path12 == null) return;
                    //v2->v3
                    PathInfo<V, E> path23 = getPathInfo(v2, v3, paths);
                    if (path23 == null) return;
                    //v1->v3
                    PathInfo<V, E> path13 = getPathInfo(v1, v3, paths);

                    E newWeight = weightManager.add(path12.weight, path23.weight);
                    if (path13 != null && weightManager.compare(newWeight, path13.weight) >= 0) return;

                    if (path13 == null) {
                        path13 = new PathInfo<>();
                        paths.get(v1).put(v3, path13);
                    } else {
                        path13.edgeInfos.clear();
                    }

                    path13.weight = newWeight;
                    path13.edgeInfos.addAll(path12.edgeInfos);
                    path13.edgeInfos.addAll(path23.edgeInfos);

                });
            });
        });
        return paths;
    }

    private PathInfo<V, E> getPathInfo(V from, V to, Map<V, Map<V, PathInfo<V, E>>> paths) {
        Map<V, PathInfo<V, E>> map = paths.get(from);
        return map == null ? null : map.get(to);
    }

    //    @Override
//    public Map<V, E> shortesPath(V begin) {
//        Vertex<V, E> beginVertex = vertics.get(begin);
//        if (beginVertex == null) return null;
//
//        Map<V, E> selectedPaths = new HashMap<>();
//        Map<Vertex<V, E>, E> paths = new HashMap<>();
//        //初始化paths
//        for (Edge<V, E> edge : beginVertex.outEdges) {
//            paths.put(edge.to, edge.weight);
//        }
//
//        while (!paths.isEmpty()) {
//            Map.Entry<Vertex<V, E>, E> minEntry = getMinPath(paths);
//            //minPath离开桌面，对它的outEdges进行松弛操作
//            Vertex<V, E> minVertex = minEntry.getKey();
//            selectedPaths.put(minVertex.value, minEntry.getValue());
//            paths.remove(minVertex);
//            //对minVertex的outEdges进行松弛操作
//            for (Edge<V, E> edge : minVertex.outEdges) {
//                //如果edge.to一离开桌面，就没有必要再次离开桌面
//                if (selectedPaths.containsKey(edge.to.value)) continue;
//                //新的可选择的最短路径 beginVertex到edge.from的最短路径 + edge.weight
//                E newWeight = weightManager.add(minEntry.getValue(), edge.weight);
//                //以前的最短路径，beginVertex到edge.to的最短路径
//                E oldWeight = paths.get(edge.to);
//                if (oldWeight == null || weightManager.compare(newWeight, oldWeight) < 0) {
//                    paths.put(edge.to, newWeight);
//                }
//            }
//        }
//        selectedPaths.remove(begin);
//        return selectedPaths;
//    }
//
//    private void relax() {
//
//    }
//
//
//    private Map.Entry<Vertex<V, E>, E> getMinPath(Map<Vertex<V, E>, E> paths) {
//        Iterator<Map.Entry<Vertex<V, E>, E>> iterator = paths.entrySet().iterator();
//        Map.Entry<Vertex<V, E>, E> minEntry = iterator.next();
//        while (iterator.hasNext()) {
//            Map.Entry<Vertex<V, E>, E> entry = iterator.next();
//            if (weightManager.compare(entry.getValue(), minEntry.getValue()) < 0) {
//                minEntry = entry;
//            }
//        }
//        return minEntry;
//    }


    private static class Vertex<V, E> {
        V value;
        Set<Edge<V, E>> inEdges = new HashSet<>();
        Set<Edge<V, E>> outEdges = new HashSet<>();

        public Vertex(V value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object obj) {
            return Objects.equals(value, ((Vertex<V, E>) obj).value);
        }

        @Override
        public int hashCode() {
            return value == null ? 0 : value.hashCode();
        }

        @Override
        public String toString() {
            return value == null ? "null" : value.toString();
        }
    }

    //E必须具备可比较性 E extends Comparable<E>
    private static class Edge<V, E> {
        Vertex<V, E> from;
        Vertex<V, E> to;
        E weight;

        public Edge(Vertex<V, E> from, Vertex<V, E> to) {
            this.from = from;
            this.to = to;
        }

        EdgeInfo<V, E> info() {
            return new EdgeInfo<>(from.value, to.value, weight);
        }

        @Override
        public boolean equals(Object obj) {
            Edge<V, E> edge = (Edge<V, E>) obj;
            return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            return from.hashCode() * 31 + to.hashCode() * 31;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }


}
